package com.problem.leetcode;

import org.openjdk.jmh.annotations.*;

import java.util.Deque;
import java.util.LinkedList;
import java.util.concurrent.TimeUnit;

/**
 * 输入: S = "loveleetcode", C = 'e'
 * 输出: [3, 2, 1, 0, 1, 0, 0, 1, 2, 2, 1, 0]
 *
 * @author didi
 * @DESCRIPTION
 * @create 2019-05-28 13:58
 **/
@State(Scope.Thread)
@BenchmarkMode({Mode.Throughput})
@Warmup(iterations = 3, time = 500, timeUnit = TimeUnit.MILLISECONDS)
@Measurement(iterations = 10, time = 5, timeUnit = TimeUnit.MICROSECONDS)
@Threads(8)
@Fork(4)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
public class Problem821 {
    public int[] shortestToChar(String S, char C) {
        int[]          resultIndex = new int[S.length()];
        int            begin       = Integer.MIN_VALUE, end = Integer.MAX_VALUE;
        Deque<Integer> list        = new LinkedList<>();
        for (int index = 0; index < S.length(); index++) {
            if (S.charAt(index) == C) {
                list.offerLast(index);
            }
        }

        list.offerFirst(begin);
        list.offerLast(end);


        begin = list.pop();
        end = list.pop();

        for (int index = 0; index < S.length(); index++) {

            if (index >= begin && index <= end) {
                resultIndex[index] = findIndex(index, begin, end);
            } else {
                begin = end;
                end = list.pop();
                --index;
            }

        }
        return resultIndex;
    }

    private int findIndex(int currentIndex, int begin, int end) {
        int middle = (begin & end) + ((begin ^ end) >> 1);
        if (currentIndex <= begin) {
            return begin - currentIndex;
        } else if (currentIndex > begin && currentIndex <= middle) {
            return currentIndex - begin;
        } else if (currentIndex > middle && currentIndex < end) {
            return end - currentIndex;
        } else {
            return currentIndex - end;
        }
    }

    @Benchmark
    public void test() {
        int[] result = this.shortestToChar("loveleetcode", 'e');
    }

    public static void main(String[] args) {
        int begin  = Integer.MAX_VALUE - 1, end = Integer.MAX_VALUE;
        int result = (begin & end) + ((begin ^ end) >> 1);
        System.out.println(result);
    }

}
